from datetime import datetime as dt
def ch(i):
    return chr(ord('A')+i)

def dg(i):
    global s
    s += 1
    if i == 0: return ch(i)
    return dg(i - 1) + ch(i) + dg(i - 1)

# 看规律，A2是A1 + B + A1
# A3是A2 + C + A2
# 很符合递归的思路。
n = int(input())
st = dt.now()
s = 0
# print(dg(n - 1))
with open('1.txt','w')as f:
    f.write(dg(n-1))
print((dt.now()-st).total_seconds(),s) # 20时0.549464s 1048575次，时间复杂度O(2**n)，空间复杂度O(1)
st = dt.now()
s = 0
# 甚至还能小小的优化一下。（这个叫记忆化搜索，使用数组来存储递归的数据，可以大大减少递归次数）
DG = ['A' if i == 0 else False for i in range(20)]
def dg1(i):
    global s
    s += 1
    if i == 0: return DG[i]
    DG[i] = dg1(i - 1)
    return DG[i] + ch(i) + DG[i]
# 之前测试的时候这里多了个dg1(n-1)...
with open('2.txt','w')as f:
    f.write(dg1(n-1))
print((dt.now()-st).total_seconds(),s) # 20时0.0s 20次，时间复杂度O(n)，空间复杂度O(n)

# PS C:\Users\lenovo\Desktop> python -m timeit -u sec -r 10 """def dg1(i):
# >>     if i == 0: return DG[i]
# >>     DG[i] = dg1(i - 1)
# >>     return DG[i] + ch(i) + DG[i]
# >> def ch(i):
# >>     return chr(ord('A')+i)
# >> DG=['A'if i==0 else False for i in range(20)]
# >> dg1(19)"""
# 200 loops, best of 10: 0.00122 sec per loop

# 其实速度也及格了，不过还是比循环稍慢一些，而且空间复杂度高出许多。

'''
什么记忆化搜索，这题用循环好吧！根本没你递归什么事！
'''
st = dt.now()
s = 0
ans = ''
for i in range(n):
    ans = ans + ch(i) + ans
    s += 1
with open('3.txt','w')as f:
    f.write(ans)
print((dt.now()-st).total_seconds(),s) # 20时0.0s 20次，时间复杂度O(n)，空间复杂度O(1)
# 0.0s就是说，运行太快了，datetime类根本统计不出来速度。我拿timeit测下试试。。
#
# PS C:\Users\lenovo\Desktop> python -m timeit -u sec -r 10 """ans = ''
# >> for i in range(20):
# >>     ans = ans + chr(ord('A')+i) + ans"""
# 200 loops, best of 10: 0.000771 sec per loop
#
# 最快0.000771s

'''
其实初始版递归和最终循环的写法几乎是一样的
递归是
def dg(i): # i 初始19，直到0，为19 -> 0
    if i == 0: return ch(i)
    return dg(i - 1) + ch(i) + dg(i - 1)

def xh(n): # n 为20的话，其实也是0 -> 19，和19 -> 0应该是一样的。
    s = ch(0)
    for i in range(1, n):
        s = s + ch(i) + s

那么为什么，循环的速度会让递归望尘莫及呢？（我之前忘了看谁的提交了，就是类似的问题，提交的递归，超时了，提交循环的好像0ms就过了？）

因为，循环是每层循环，直接使用上一层循环的结果s，一共循环n次，执行n次。

而递归，
dg(19)需要两个dg(18),dg(18)又需要两个dg(17)，最后到dg(0)的时候，大概要运行2的19次方次相同的代码。。而dg(1)的次数是他的一半，dg(2)再一半
加起来，大概是运行了2的20次方-1条语句，其中有超大量重复。

所以哦！重点来了！如果你的dg中，包含2个dg下一层，那你要小心了，它的时间复杂度很可能是O(2^(n - 1) + 2^(n - 2) + ... + 1)，简写成O(2^n)
同理，有3个递归的话，那就是O(3^(n - 1) + 3^(n - 2) + ... + 1)，简写成O(3^n)
O(x^n)啊，这比O(n^2)还猛呢吧。。。
只有当只有一个递归的时候，才是和循环差不多的O(n)，因为1的多少次方都是1.
如果实在实在不知道怎么用循环写，建议想办法用上记忆化搜索哦！典型的空间换时间！而且超值的那种！

'''

# -------------------------------------------------------------------------------

# 比赛环境为python3.8.6版本自带的IDLE，最好早点熟悉一下。。这个东西的提示时有时无

# 菜单栏最右边的Help的Python Docs 比赛时候也可以看，不过建议还是提前多了解了解，

# 比赛的时候至少知道在文档找什么能用的上。

# IDLE是下载Python时自带的，在按住win+s搜索IDLE就能搜到了。

# 然后点左上角的File可以创建新文件，然后按F5可以运行。
